//链表实现队列
struct LinkList
{
    int index;
    LinkList* next;
    LinkList* pre;
};

LinkList* newLinkList(int value)
{
    LinkList* newItem=new LinkList;
    newItem->index=value;
    newItem->next=NULL;
    newItem->pre=NULL;
    return newItem;
}

void deleteLinkList(LinkList* l)
{
    LinkList* next=l;
    while (next!=NULL)
    {
        LinkList* now=next->next;
        delete next;
        next=now;
    }
}


//链表添加新的节点
LinkList* addItemEnd(LinkList* l,LinkList* newItem)
{
    if(l==NULL)
    {
        l=newItem;   
    }
    else{
        l->next=newItem;
    }
    return newItem;
}


//无限长度的队列 必须要用链表实现
struct Queue
{
    LinkList* start; //队列起点
    LinkList* end;   //队列终点
    int size;//队列元素个数
};

Queue* newQueue()
{
    Queue* q=new Queue;
    q->size=0;
    q->start=NULL;
    q->end=NULL;
    return q;
}

//清空队列
void deleteQueue(Queue* q)
{
    deleteLinkList(q->start);
    delete q;
}

//入队
void inqueue(Queue* q,LinkList* newItem){
    LinkList* end=addItemEnd(q->end,newItem);
    q->end=end;
    if(q->start==NULL)
    {
        q->start=end;
    }
    q->size++;
}

//出队
LinkList* dequeen(Queue* q){
    if(q->start==NULL)
    {
        return NULL;
    }
    else{
        LinkList* l=q->start;
        q->start=l->next;
        q->size--;
        return l;
    }
}

//队列元素多少
int sizeOfQueue(Queue* q)
{
    return q->size;
}

//队列是否为空
int isEmpQueue(Queue* q)
{
    return q->size==0;
}